An ad hoc communication scheme in which communication nodes directly communicate with each other has been used as a scheme for communication among a plurality of terminals. A proactive scheme and a reactive scheme are known as systems to construct routes in ad hoc communication.
In the proactive scheme, each node on a network bidirectionally communicates using a hello frame (exchanges a hello frame) with the adjacent node to notify the adjacent node of its own existence and recognize the existence of the adjacent node. A link can be established at a point when both adjacent nodes become able to manage each other by exchanging their hello frames. The hello frames are exchanged in regular one-hop broadcast. The nodes on a network each exchange hello frames including route information to the destination node, whereby routes are constructed between the transmission source node and the destination node (gateway node, for example).
FIG. 11 is a block diagram illustrating a configuration of a node 200 that performs communication in a proactive scheme, in the related technique. The node 200 includes a communicating unit 201, a link quality evaluating unit 202, a link table holding unit 203, a route constructing unit 204, and a routing table holding unit 205.
The communicating unit 201 performs wired or wireless communication with nodes external to the node 200. The link quality evaluating unit 202 creates a link table from quality information of hello frames received at the communicating unit 201 and outputs the link table to the link table holding unit 203 as well as outputting information on the link quality to the route constructing unit 204. The link table holding unit 203 holds, as a table, link information of each node that is created by the link quality evaluating unit 202, based on the quality information of the hello frames received at the communicating unit 201. The route constructing unit 204 constructs routes based on the information on the link quality input from the link quality evaluating unit 202, creates route information for each target node, and outputs it to the routing table holding unit 205. The routing table holding unit 205 holds, as a table, route information output from the route constructing unit 204.
By contrast, a reactive scheme is a system to perform routing when a data transmission source node transmits data. In the reactive scheme, the transmission source node searches for an optimal route immediately before routing, whereby routes are constructed. In the route construction in the reactive scheme, each node on a network broadcasts a frame called a route request (RREQ) to surrounding nodes in order to find an optimal route. When the RREQ reaches the target node (gateway node, for example), the node creates a route reply (RREP) frame and returns (unicasts) the RREP by following the route through which the RREQ has been transmitted. This constructs a bidirectional communication route between the transmission source node and the target node, and subsequently, data is transferred via the nodes on the communication route for transmission and reception.
In the aforementioned reactive scheme, an RREQ is broadcasted to construct a route. When route construction is performed on a plurality of nodes at the same time, a plurality of RREQs are broadcasted to connect each of the nodes. This may cause network congestions. The following technique is known as a technique to construct a route in an ad hoc network. When nodes each transfer a frame in the upstream direction, a table for route construction in the upstream direction is created based on a frame transfer cost value between the nodes. In addition to this, a routing table for the downstream direction is created and is utilized in communication in the downstream direction to reduce the communication volume in the route construction in downstream communication (Japanese Laid-open Patent Publication No. 2011-097458, for example).
In the configuration of an ad hoc network with a large number of nodes, it is important to form a network in which all nodes can communicate with the target destination by intercommunication among the nodes with reduced hardware resources (and with reduced costs in relation to these resources). In a proactive scheme, each node on a network can reduce the communication volume for the route construction by exchanging hello frames constantly, as compared with a reactive scheme. However, some arrangements of the nodes use a large amount of memory to hold a link table, in association with transmission and reception of hello packets. Depending on the arrangement of the nodes (the number of surrounding nodes), the amount of memory requested to hold the link table may exceed the amount of memory of the nodes.
FIG. 12 is a schematic for illustrating an issue in a route construction in the related proactive scheme. In FIG. 12, a gateway (GW) node 101 and nodes 102 to 115 are directly or indirectly connected with each other to form an ad hoc network system 100. As illustrated in FIG. 12, the arrangement of the nodes in the ad hoc network system 100 is not uniform, and has a solid line area A3 in which the nodes are arranged with high density and a broken line area A4 in which the node is arranged with low density. This means that the ad hoc network system 100 includes a node (the node 104, for example) having a larger number of adjacent nodes and a node (the node 103 or the node 108, for example) having a smaller number of adjacent nodes.
In FIG. 12, each of the nodes exchanges hello frames to recognize the adjacent node. However, for example, the node 104 is adjacent to a total of five nodes and it is difficult for the node 104 to hold, in a link table, information of the hello frames from all of the adjacent nodes. In this case, the node 104 holds the information in the link table in the order of communication quality with the nodes.
As illustrated in FIG. 12, a link L108 is the only route from the node 108 to the node 104 and no alternative route exists. When the quality of the link L108 is not favorable, the node 108 may be absent from a link management list of the node 104 due to limitation of the amount of memory. For example, the node 104 exchanges hello frames with a plurality of surrounding nodes 106, 111, and 113 that belong to the solid line area A3. Due to the exchange, when the number of adjacent nodes to be managed by the node 104 exceeds the upper limit, no management on adjacent nodes through the exchange of hello frames is performed on the node 108. As a result, the node 104 fails to recognize the node 108 as an adjacent node. Although the node 108 can recognize the node 104, it is difficult for the link L108 between the node 104 and the node 108 to utilize as a communication route. The node 108 has no other routes except the route that passes through the node 104. Specifically, even when communication through the link L108 is possible, when the node 104 has a large number of adjacent nodes, the node 108 fails to utilize a route via the node 104 to be isolated.